/*
 * Copyright (C) 2015 soud
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
 * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "erupt.h"
#include "parser.h"

static ast_node_t *parse_fn(token_t *ts);
static ast_node_t *parse_ident(token_t *ts);
static ast_node_t *parse_fn_proto(token_t *ts);
static ast_node_list_t *parse_fn_params(token_t *ts);
static ast_node_t *parse_call(token_t *ts);
static ast_node_t *parse_var(token_t *ts);
static ast_node_t *parse_if(token_t *ts);
static ast_node_t *parse_expr(token_t *ts, tokentype delimiter);
static ast_node_t *rpnstack_to_ast(stack_t *rpn);
static void emit_node(ast_node_list_t *nl, ast_node_t *node);
static token_t *peek(token_t *ts);
static token_t *eat(token_t *ts);

bool PARSE_FAILED = false;

static const struct {
        char *name;
        ast_type_t type;
} data_types[] = {
        {INT_KEYWORD    , INT},
        {I8_KEYWORD     , I8},
        {I16_KEYWORD    , I16},
        {I32_KEYWORD    , I32},
        {I64_KEYWORD    , I64},
        {U8_KEYWORD     , U8},
        {U16_KEYWORD    , U16},
        {U32_KEYWORD    , U32},
        {U64_KEYWORD    , U64},
        {STRING_KEYWORD , STR},
        {CHAR_KEYWORD   , CHAR},
        {BOOL_KEYWORD   , BOOL},
        {FLOAT_KEYWORD  , FLOAT},
        {F32_KEYWORD    , F32},
        {F64_KEYWORD    , F64},
        {NONE_KEYWORD   , NONE}
};

static const ast_op_t operators[] = {
        /* assignment operators */
        {TOKEN_EQ        , 0  , ASSOC_NONE  , false},
        {TOKEN_PLUS_EQ   , 0  , ASSOC_NONE  , false},
        {TOKEN_MIN_EQ    , 0  , ASSOC_NONE  , false},
        {TOKEN_STAR_EQ   , 0  , ASSOC_NONE  , false},
        {TOKEN_SLASH_EQ  , 0  , ASSOC_NONE  , false},
        {TOKEN_MOD_EQ    , 0  , ASSOC_NONE  , false},
        {TOKEN_B_AND_EQ  , 0  , ASSOC_NONE  , false},
        {TOKEN_B_OR_EQ   , 0  , ASSOC_NONE  , false},
        {TOKEN_B_XOR_EQ  , 0  , ASSOC_NONE  , false},

        /* (bitwise) logical operators */
        {TOKEN_OR        , 1  , ASSOC_RIGHT , false},
        {TOKEN_AND       , 2  , ASSOC_RIGHT , false},
        {TOKEN_B_OR      , 3  , ASSOC_RIGHT , false},
        {TOKEN_B_XOR     , 4  , ASSOC_RIGHT , false},
        {TOKEN_B_AND     , 5  , ASSOC_RIGHT , false},

        /* comparison operators */
        {TOKEN_EQ_EQ     , 6  , ASSOC_LEFT  , false},
        {TOKEN_NOT_EQ    , 6  , ASSOC_LEFT  , false},
        {TOKEN_LT        , 7  , ASSOC_LEFT  , false},
        {TOKEN_GT        , 7  , ASSOC_LEFT  , false},
        {TOKEN_LT_EQ     , 7  , ASSOC_LEFT  , false},
        {TOKEN_GT_EQ     , 7  , ASSOC_LEFT  , false},

        /* bitwise shifts */
        {TOKEN_L_SHIFT   , 7  , ASSOC_RIGHT , false},
        {TOKEN_R_SHIFT   , 7  , ASSOC_RIGHT , false},

        /* mathematical operators */
        {TOKEN_PLUS      , 9  , ASSOC_LEFT  , false},
        {TOKEN_MIN       , 9  , ASSOC_LEFT  , false},
        {TOKEN_STAR      , 10 , ASSOC_LEFT  , false},
        {TOKEN_SLASH     , 10 , ASSOC_LEFT  , false},
        {TOKEN_MOD       , 10 , ASSOC_LEFT  , false},
        {TOKEN_STAR_STAR , 11 , ASSOC_RIGHT , false},

        /* unary operators */
        {TOKEN_MIN       , 12 , ASSOC_RIGHT , true},
        {TOKEN_BANG      , 12 , ASSOC_RIGHT , true},
        {TOKEN_B_NOT     , 12 , ASSOC_RIGHT , true},

        /* misc */
        {TOKEN_L_PAREN   , 20 , ASSOC_NONE  , false}
};

static bool is_operator(tokentype token)
{
        size_t ops_len = sizeof(operators) / sizeof(operators[0]);

        for (size_t i = 0; i < ops_len; ++i)
                if (token == operators[i].symbol)
                        return true;

        return false;
}

static const ast_op_t *get_operator(tokentype token)
{
        size_t ops_len = sizeof(operators) / sizeof(operators[0]);

        for (size_t i = 0; i < ops_len; ++i)
                if (token == operators[i].symbol)
                        return &operators[i];

        return NULL;
}

static ast_type_t get_type(char *name)
{
        size_t types_len = sizeof(data_types) / sizeof(data_types[0]);

        for (size_t i = 0; i < types_len; ++i)
                if (strcmp(data_types[i].name, name) == 0)
                        return data_types[i].type;

        return UNKNOWN;
}

/*
 * parse a top level declaration
 *
 * possible syntax:
 *         fun function() ...
 *         mut Int32 var ...
 *         use module ...
 *
 * any other declaration wil fail as these are the only declarations allowed at
 * top level
 */
static ast_node_t *parse_top_level(token_t *ts)
{
        switch (ts->type) {
        case TOKEN_FUNCTION:
                return parse_fn(ts);
        case TOKEN_MUTABLE:
        case TOKEN_IDENT:
                return parse_var(ts);
        case TOKEN_IMPORT:
                /* TODO: parse import */
        default:
                parser_file_error(ts->line_n, "unexpected '%s'\n", ts->value);
        }

        return NULL;
}

/*
 * parse a block level declaration
 *
 * possible syntax:
 *      mut Char var ...
 *      x += 3
 *      if x < 5 ... | unless x < 5 ...
 *      while x < 5 ...
 *      return x
 */
static ast_node_t *parse_block_level(token_t *ts)
{
        switch (ts->type) {
        case TOKEN_MUTABLE:
                return parse_var(ts);
        case TOKEN_IDENT:
                return parse_ident(ts);
        case TOKEN_UNLESS:
        case TOKEN_IF:
                return parse_if(ts);
        case TOKEN_WHILE:
                /* TODO: parse while */
        case TOKEN_RETURN:
                /* TODO: parse return */
        case TOKEN_EOF:
                file_fatal_error(ts->line_n, "unclosed block\n");
        default:
                parser_file_error(ts->line_n, "unexpected '%s'\n", ts->value);
        }

        return NULL;
}

static ast_node_list_t *parse_block(token_t *ts)
{
        /* eat the { */
        eat(ts);

        /* empty body */
        if (ts->type == TOKEN_R_BRACE) {
                file_warning(ts->line_n, "empty block\n");
                return NULL;
        }

        ast_node_list_t *nl = create_node_list();

        while (ts->type != TOKEN_R_BRACE) {
                emit_node(nl, parse_block_level(ts));
                eat(ts);
        }

        return nl;
}

ast_node_list_t *parse_token_stream(token_t *ts)
{
        ast_node_list_t *nl = create_node_list();
        verbose_printf("generating abstract syntax tree\n");

        do {
                emit_node(nl, parse_top_level(ts));
                eat(ts);
        } while (ts->type != TOKEN_EOF);

        return nl;
}

/* fun func(...) { ... } */
static ast_node_t *parse_fn(token_t *ts)
{
        ast_node_t *prototype = parse_fn_proto(ts);
        ast_node_list_t *body = NULL;

        if (ts->type == TOKEN_SEMI_COLON) {
                eat(ts);
                return prototype;
        } else if (ts->type == TOKEN_L_BRACE) {
                body = parse_block(ts);
        } else {
                parser_file_error(ts->line_n, "expected semi-colon or block");
        }

        return create_fn(prototype, body);
}

/*
 * func(...)
 * Str var = ....
 * var += 5;
 */
static ast_node_t *parse_ident(token_t *ts)
{
        if (peek(ts)->type == TOKEN_L_PAREN)
                return parse_call(ts);

        if (is_operator(peek(ts)->type))
                return parse_expr(ts, TOKEN_SEMI_COLON);

        return parse_var(ts);
}

/*
 * a token in an expression can be either an identifier or number. this creates
 * the appropriate one
 */
static ast_node_t *parse_expr_val(token_t token)
{
        if (token.type == TOKEN_IDENT)
                return create_var(token.value, UNKNOWN, NULL, NULL);

        if (token.type == TOKEN_NUMBER)
                return create_number(strtof(token.value, NULL));

        return NULL;
}

/*
 * fun func(...) -> Int32 ...
 * fun func(...) ...
 * fun func ...
 */
static ast_node_t *parse_fn_proto(token_t *ts)
{
        ast_type_t data_type = NONE;
        char *name;
        ast_node_list_t *args = NULL;

        /* eat function declaration token */
        eat(ts);

        if (ts->type != TOKEN_IDENT)
                parser_file_error(ts->line_n, "illegal function name '%s'", ts->value);

        name = ts->value;

        if (peek(ts)->type == TOKEN_L_PAREN)
                parse_fn_params(ts);
        else if (peek(ts)->type == TOKEN_R_PAREN)
                eat(ts);

        /* get return type (if there is one) */
        if (peek(ts)->type == TOKEN_R_ARROW) {
                eat(ts);
                if ((data_type = get_type(eat(ts)->value)) == UNKNOWN)
                        parser_file_error(ts->line_n, "unknown data type '%s' function '%s'\n",
                                          ts->value, name);
        } else {
                /* warn the user if a function besides main doesnt explicitly declare a return type */
                if (strcmp(name, "main") != 0)
                        file_warning(ts->line_n, "function '%s' has no return type set\n", name);
        }

        /* eat the ) or type declaration token */
        eat(ts);

        return create_fn_proto(name, args, data_type);
}

static ast_node_list_t *parse_fn_params(token_t *ts)
{
        if (ts->type == TOKEN_EOF)
                parser_file_error(ts->line_n, "unclosed function parameters\n");

        while (ts->type != TOKEN_R_PAREN)
                eat(ts);

        return NULL;
}

/* function_call(...) */
static ast_node_t *parse_call(token_t *ts)
{
        char *name = ts->value;
        /* TODO: parse args */
        ast_node_list_t *args = NULL;

        return create_call(name, args);
}

/*
 * Int32 var;
 * Int32 var = ...
 * mut Int32 var = ...
 */
static ast_node_t *parse_var(token_t *ts)
{
        char *name;
        bool mutable = ts->type == TOKEN_MUTABLE;
        ast_type_t type = UNKNOWN;

        if (ts->type == TOKEN_MUTABLE)
                eat(ts);

        if ((type = get_type(ts->value)) == UNKNOWN)
                parser_file_error(ts->line_n, "unknown data type '%s'\n", ts->value);

        if (eat(ts)->type != TOKEN_IDENT)
                parser_file_error(ts->line_n, "illegal variable name '%s'\n", ts->value);

        name = ts->value;

        eat(ts);

        if (ts->type == TOKEN_SEMI_COLON)
                return create_var(name, type, mutable, NULL);
        else if (is_operator(ts->type))
                return create_var(name, type, mutable, parse_expr(ts, TOKEN_SEMI_COLON));

        parser_file_error(ts->line_n, "expected semi-colon or assignment, got '%s'\n", ts->value);
        return create_var(name, type, mutable, NULL);
}

static ast_node_t *parse_if(token_t *ts)
{
        /* if the unless statement is used instead of if, swap the true and
           false body at the end */
        bool swap = ts->type == TOKEN_UNLESS;

        ast_node_t *condition = NULL;
        ast_node_list_t *true_body = NULL;
        ast_node_list_t *false_body = NULL;

        condition = parse_expr(ts, TOKEN_R_BRACE);
        true_body = parse_block(ts);

        if (ts->type == TOKEN_ELSE) {
                eat(ts);
                false_body = parse_block(ts);
        }

        if (swap)
                swap_lists(true_body, false_body);

        return create_if(condition, true_body, false_body);
}

static ast_node_t *parse_expr(token_t *ts, tokentype delimiter)
{
        /* shut up when an error gets printed so we don't spam the console */
        bool shut_up = false;
        size_t line_start = ts->line_n;
        stack_t *operators = smalloc(sizeof(stack_t));
        stack_t *output = smalloc(sizeof(stack_t));

        for (token_t prev = NULL_TOKEN; ts->type != delimiter; prev = *ts, eat(ts)) {
                if (is_operator(ts->type)) {
                        /* an identifier or number is expected after an
                           operator, except when the current operator is
                           anything but left-associated */
                        if (is_operator(prev.type) &&
                            get_operator(ts->type)->assoc == ASSOC_LEFT) {
                                if (!shut_up) {
                                        parser_file_error(ts->line_n, "unexpected '%s' in expression\n",
                                                          ts->value);
                                        shut_up = true;
                                }
                        }
                        if (stack_size(operators) >= 2 &&
                            get_operator(ts->type)->assoc == ASSOC_LEFT &&
                            get_operator(ts->type)->precedence >=
                            get_operator(stack_top(&operators).type)->precedence) {
                                stack_push(&output, stack_pop(&operators));
                        }

                        stack_push(&operators, *ts);
                } else if (ts->type == TOKEN_IDENT || ts->type == TOKEN_NUMBER) {
                        /* an operator is expected after an identifier, number
                           or (. any other token is invalid */
                        if ((prev.type == TOKEN_IDENT || prev.type == TOKEN_NUMBER ||
                            prev.type == TOKEN_R_PAREN) && !shut_up) {
                                parser_file_error(ts->line_n, "unexpected '%s' in expression\n",
                                                  ts->value);
                                shut_up = true;
                        }
                        stack_push(&output, *ts);
                } else if (ts->type == TOKEN_IF || ts->type == TOKEN_UNLESS) {
                        bool is_unless = ts->type == TOKEN_UNLESS;

                        eat(ts);

                        /* TODO: shorthand if/unless */
                        return create_if(parse_expr(ts, TOKEN_SEMI_COLON), NULL, NULL);
                } else if (ts->type == TOKEN_R_PAREN) {
                        /* pop all operators to output stack until ( is found */
                        while (stack_top(&operators).type != TOKEN_L_PAREN) {
                                if (!stack_top(&operators).type && !shut_up) {
                                        parser_file_error(ts->line_n, "unmatched ')' in expression\n");
                                        shut_up = true;
                                        break;
                                }

                                stack_push(&output, stack_pop(&operators));
                        }

                        /* pop the remaining ( */
                        stack_pop(&operators);
                } else {
                        if (ts->type == TOKEN_EOF)
                                file_fatal_error(line_start, "unterminated expression\n");

                        if (!shut_up) {
                                parser_file_error(ts->line_n, "unexpected token '%s' in expression\n",
                                                  ts->value);
                                shut_up = true;
                        }
                }
        }

        /* any remaining operators get pushed to output */
        while (stack_size(operators))
                stack_push(&output, stack_pop(&operators));

        stack_dump(output);

        return rpnstack_to_ast(output);
}

static ast_node_t *rpnstack_to_ast(stack_t *rpn)
{
        if (!rpn)
                return NULL;

        ast_node_t *expression;

        do {
                printf("%s\n", stack_pop(&rpn).value);
        } while (stack_size(rpn));

        return expression;
}

static void emit_node(ast_node_list_t *nl, ast_node_t *node)
{
        /* node could be NULL in some context, such as import */
        if (!node)
                return;

        if (!nl->node) {
                nl->node = node;
                return;
        }

        while (nl->next)
                nl = nl->next;

        nl->next = smalloc(sizeof(ast_node_list_t));
        nl->next->node = node;
        nl->next->next = NULL;
}

static token_t *peek(token_t *ts)
{
        return ts->next;
}

static token_t *eat(token_t *ts)
{
        if (ts->next == NULL)
                return NULL;

        *ts = *ts->next;

        return ts;
}
